package com.example.array;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。
 * 例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
 *  给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
 *
 *  示例 1：
 *  输入：A = [1,2,0,0], K = 34
 * 输出：[1,2,3,4]
 * 解释：1200 + 34 = 1234
 *
 *  示例 2：
 *  输入：A = [2,7,4], K = 181
 * 输出：[4,5,5]
 * 解释：274 + 181 = 455
 */
public class Leetcode989_AddToArrayForm {
    public static void main(String[] args) {
        int[] num = {1, 2, 0, 0};
        int k = 34;
//        num = new int[] {2, 7, 4};
//        k = 181;
//        num = new int[] {9, 9, 9, 9, 9, 9, 9, 9, 9, 9};
//        k = 1;
//        num = new int[] {0};
//        k = 17;
//        num = new int[] {3};
//        k = 17;
        num = new int[] {5, 5};
        k = 973;
        List<Integer> res = new Solution().addToArrayForm(num, k);
        res.forEach(e -> System.out.println(e));
    }

    static class Solution {
        /**
         * 将整个加数加入数组表示的数的最低位，通过求余数计算留下来的数值，求除数计算进位数值；
         * @param num
         * @param k
         * @return
         */
        private List<Integer> addToArrayForm3(int[] num, int k) {
            int N = num.length;
            int cur = k;
            List ans = new ArrayList();

            int i = N;
            while (--i >= 0 || cur > 0) {
                if (i >= 0)
                    cur += num[i];
                ans.add(cur % 10);
                cur /= 10;
            }
            Collections.reverse(ans);
            return ans;
        }

        /**
         * 解法二:求k中的每位数字同时与num的每位相加
         * @param num
         * @param k
         * @return
         */
        private List<Integer> addToArrayForm2(int[] num, int k) {
            // {3} , 17
            List<Integer> res = new ArrayList<>();
            int i = num.length -1;
            int last = k % 10;
            int carry = 0;
            while (i >= 0 || last != k) {
                int n1 = i >= 0 ? num[i--] : 0;
                int n2 = last;
                int sum = n1 + n2 + carry;
                res.add(sum % 10);
                carry = sum / 10;
                k /= 10;
                last = k % 10;
            }

            // 最高位处理
            if (last != 0 || carry != 0) {
                res.add((carry + last) % 10);
                carry = (carry + last) / 10;
            }

            if (carry != 0) res.add(carry);

            Collections.reverse(res);
            return res;
        }
        /**
         * 解法一:先将k的每位数单独取出来,然后和nuu里面每一位相加
         * @param num
         * @param k
         * @return
         */
        private List<Integer> addToArrayForm1(int[] num, int k) {
            Deque<Integer> kList = new LinkedList<>();
            Deque<Integer> res = new LinkedList<>();
            int last = k % 10;
            while (last != k) {
                kList.addFirst(last);
                k /= 10;
                last = k % 10;
            }
            if (last != 0) kList.addFirst(last);

            int i = num.length - 1;
            int carry = 0;
            while (i >= 0 || !kList.isEmpty()) {
                int n1 = i >= 0 ? num[i--] : 0;
                int n2 = kList.isEmpty() ? 0 : kList.removeLast();
                int sum = n1 + n2 + carry;
                res.addFirst(sum % 10);
                carry = sum / 10;
            }
            if (carry != 0) res.addFirst(carry);
            return (List<Integer>) res;
//            return res.stream().collect(Collectors.toList());
        }

        public List<Integer> addToArrayForm(int[] num, int k) {
            return addToArrayForm2(num, k);
        }
    }
}
